package Leetcode.Dichotomy;

/**
 * @Author: kirito
 * @Date: 2024/4/3 17:26
 * @Description:
 * 使结果不超过阈值的最小除数
 * 给你一个整数数组 nums 和一个正整数 threshold  ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。
 *
 * 请你找出能够使上述结果小于等于阈值 threshold 的除数中 最小 的那个。
 *
 * 每个数除以除数后都向上取整，比方说 7/3 = 3 ， 10/2 = 5 。
 *
 * 题目保证一定有解。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,5,9], threshold = 6
 * 输出：5
 * 解释：如果除数为 1 ，我们可以得到和为 17 （1+2+5+9）。
 * 如果除数为 4 ，我们可以得到和为 7 (1+1+2+3) 。如果除数为 5 ，和为 5 (1+1+1+2)。
 * 示例 2：
 *
 * 输入：nums = [2,3,5,7,11], threshold = 11
 * 输出：3
 * 示例 3：
 *
 * 输入：nums = [19], threshold = 5
 * 输出：4
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 5 * 10^4
 * 1 <= nums[i] <= 10^6
 * nums.length <= threshold <= 10^6
 */

public class smallestDivisor {
    public static void main(String[] args) {
        int[] nums = {1, 2, 5, 9};
        int threshold = 6;
        System.out.println(smallestDivisor(nums, threshold));
    }

    public static int smallestDivisor(int[] nums, int threshold) {
        int left = 1;
        // int right = nums[nums.length-1];     // 当nums数组是有序, nums数组中最大值是最后一位
        int right = Integer.MIN_VALUE;          // 当nums数组是无序, 扫描查找最大值
        for (int num: nums) {
            right = Math.max(right, num);
        }
        // PS: 面试找最大值不要使用Collections.max(), 别问我是怎么知道的

        // 注意循环条件, 如果循环条件为(left < right), left和right重叠时会跳出循环
        while (left <= right) {
            // 计算mid, 小心溢出
//            int mid = (left + right) / 2;               // 方法一  会溢出
             int mid = left + (right - left) / 2;     // 方法二  无溢出
            // int mid = left + (right - left) >> 1;    // 方法三  无溢出

            int sum = findDivisor(nums, mid);

            if (sum > threshold) {
                left = mid + 1;         // 右区间 (mid, right]
            } else {
                right = mid - 1;        // 左区间 [left, mid)
            }
        }
        return left;
    }

    public static int findDivisor(int[] nums, int divisor) {
        int sum = 0;
        for (int num: nums) {
            sum += (num / divisor) + (num % divisor == 0 ? 0 : 1);
        }
        return sum;
    }
}
